A cyclic redundancy check (CRC) is a widely used technique wherein a particular polynomial is used to assure data reliability. The CRC may be used to protect blocks of data called frames or cells wherein, the transmitter appends an extra n-bit sequence called a frame check sequence (FCS). The FCS holds redundant information about the frame that helps the receiver detect errors.
For example, some commonly used polynomials for CRC calculations are:                CRC-12: X12+X11+X3+X2+X+1,        CRC-16: X16+X15+X2+1,        CRC-CCITT: X16+X12+X5+1,        CRC-32: X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1.        
CRC-32, for example, generates a 32-bit FCS, which is used by the local network standards committee (IEEE-802) and some Department of Defense (DOD) applications. The same algorithm or hardware may be used to compute the FCS or to check the data using the FCS. By appending an extra n-bit sequence of zeroes to the data as input, an FCS will be produced as output. By appending the n-bit FCS sequence to the data as input, an n-bit sequence of zeroes will be produced as output if there are no transmission errors.
A network processor may perform CRC calculations as a transmitter and/or as a receiver for multiple frames or cells of one data packet or of multiple data packets. These packets may be of various different internetworking protocols or of one particular internetworking protocol. For example, Asynchronous Transfer Mode (ATM) is a set of protocols that use the concept of a connection and require ATM specific signaling protocols and addressing structures, as well as protocols to route ATM connection requests across an ATM network. A virtual circuit is set up across the ATM network prior to transferring data. ATM circuits can be virtual paths, identified by a virtual path identifier (VPI) or virtual channels, identified by the combination of a VPI and a virtual channel identifier (VCI). A virtual path is a bundle of virtual channels with a common VPI.
A typical network processor while operating as an ATM switch receives a cell of a specific VCI/VPI value; looks up the connection value in a local connection table to retrieve an associated CRC residue, identify an outgoing port and optionally get a new VPI/VCI value for that particular connection; calculates a new CRC residue for the connection to update the local connection table, and retransmits the cell on that outgoing link with appropriate connection identifiers. For example, one of the more common ATM Adaptation Layers (AAL) used to transmit data across ATM networks is called AAL5. AAL5 requires packets transmitted using a particular connection to be received in sequence, without interleaving cells of different packets on the same connection so that the receiver will be able to reconstruct the packet. Updating the CRC residue for the connection, permits sequential CRC calculations for the packet. Unfortunately, as the network processor may be handling a large number of connections, the local table may become rather large, and latencies for repeated accesses to retrieve and to update CRC residues may represent a significant fraction of time in processing the packet.
Some network processors have provided for switching between multiple software threads of execution to permit access latencies to overlap with useful computations. Commonly though, cases may arise in which adjacent software threads may be processing sequential cells of the same connection as shown with reference to adjacent threads 301 and 302 of FIG. 3. In such cases, an access 315 to retrieve an updated CRC residue must necessarily be performed sequentially with respect to the access 314 that updates the CRC residue. Therefore, potential throughput of the network processor may be limited by the frequency of occurrence of these cases. Unfortunately, the frequency may be rather high for some commonly used AALs (like AAL5 for example).